package org.aplombh.java.leetcode.all;

import java.util.*;

public class _39组合总数 {
    public static void main(String[] args) {
        new Solution39_1().combinationSum(new int[]{1, 2, 3, 6, 7}, 7);
    }
}

class Solution39_1 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> combine = new ArrayList<>();
        dfs(candidates, 0, target, res, combine);
        return res;
    }

    public void dfs(int[] candidates, int idx, int target, List<List<Integer>> res, List<Integer> path) {

        // 到最后一个
        if (idx == candidates.length) {
            return;
        }

        // 满足条件
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 直接跳过
        dfs(candidates, idx + 1, target, res, path);

        // 选择当前数
        if (target - candidates[idx] >= 0) {
            path.add(candidates[idx]);
            dfs(candidates, idx, target - candidates[idx], res, path);
            path.remove(path.size() - 1);
        }
    }
}
